\section{栈和队列}
栈 (Stack)：运算只在表的一端进行。 队列 (Queue)：运算只在表的两端进行。

栈的抽象数据类型
\begin{cpp}
	template <typename T>
	class Stack {
			public:                     //栈的运算集
			void clear();               //变为空栈
			bool push(const T item);    //item入栈,成功返回真,否则假
			bool pop(T& item);          //返回栈顶内容并弹出,成功返回真,否则假
			bool top(T& item);          //返回栈顶但不弹出,成功返回真,否则假
			bool isEmpty();             //若栈已空返回真
			bool isFull();              //若栈已满返回真
		};
\end{cpp}
顺序栈 (Array-based Stack)
\begin{itemize}
	\item 使用向量实现,本质上是顺序表的简化版
	\item 关键是确定哪一端作为栈顶
	\item 上溢 (Overflow)当栈中已经有maxsize个元素时,如果再做进栈
	      运算,所产生的现象
	      下溢 (Underflow) 对空栈进行出栈运算时所产生的现象,下溢问题
\end{itemize}
\textbf{链式栈(Linked Stack)}用单链表方式存储,其中指针的方向是从栈顶向下
链接
\textbf{压栈操作代码框架}\\
\begin{cpp}
	bool arrStack<T>::push(const T item) {
			if (top == mSize-1) {    // 栈已满
					cout << "栈满溢出" << endl;
					return false;
				} else {       // 新元素入栈并修改栈顶指针
					st[++top] = item;
					return true;
				}
		}
\end{cpp}
\textbf{栈顶操作代码框架}
\begin{cpp}
	bool arrStack<T>::pop(T & item) { // 出栈
			if (top == -1) {                  // 栈为空
					cout << "栈为空,不能执行出栈操作"<< endl;
					return false;
				} else {
					item = st[top--]; // 返回栈顶,并缩减1
					return true;
				}
		}
\end{cpp}
顺序栈的实现：
\cppfile{code/DS/ex7/Stack.hpp}
测试代码：
\cppfile{code/DS/ex7/main.cpp}
\textbf{链式栈的定义}\\
用单链表方式存储，指针的方向从栈顶向下链接。示意图如\ref{fig:ds_16}
\begin{figure}[!htb]\label{fig:ds_16}
	\centering
	\includegraphics[width=0.5\textwidth]{ds_16.png}
	\caption{链式栈示意图}
\end{figure}
\textbf{链式栈创建}
\begin{cpp}
	template <class T> class lnkStack <T>{
			private:                    // 栈的链式存储
			Link<T>* top;               // 指向栈顶的指针
			int size;                   // 存放元素的个数
			public:                     // 栈运算的链式实现
			lnkStack(int defSize) {     // 构造函数
					top = NULL; size = 0;
				}
			~lnkStack() {           //析构函数
					clear();
				}
		}
\end{cpp}

压入栈顶

\begin{cpp}
	// 入栈操作的链式实现
	bool lnksStack<T>:: push(const T item) {
			Link<T>* tmp = new Link<T>(item, top);
			top = tmp;
			size++;
			return true;
		}
	Link(const T info, Link* nextValue){ // 具有两个参数的Link构造函数
			data = info;
			next = nextValue;
		}
\end{cpp}
从单链栈弹出元素
\begin{cpp}
	// 出栈操作的链式实现
	bool lnkStack<T>:: pop(T& item) {
			Link <T> *tmp;
			if (size == 0) {
					cout << "栈为空,不能执行出栈操作"<< endl;
					return false;
				}
			item = top->data;
			tmp = top->next;
			delete top;
			top = tmp;
			size--;
			return true;
		}
\end{cpp}
\textbf{顺序栈和链式栈的比较}
\begin{itemize}
	\item  时间效率
	      \begin{itemize}
		      \item 所有操作都只需常数时间
		      \item 顺序栈和链式栈在时间效率上难分伯仲
	      \end{itemize}
	\item 空间效率
	      \begin{itemize}
		      \item 顺序栈须说明一个固定的长度
		      \item 链式栈的长度可变,但增加结构性开销
	      \end{itemize}
\end{itemize}
实际应用中,顺序栈比链式栈用得更广泛：
\begin{itemize}
	\item  顺序栈容易根据栈顶位置,进行相对位移,快速定位并读取栈的内部元素
	\item – 顺序栈读取内部元素的时间为O(1),而链式栈则需要沿着指针链游走,显然慢些,读取第kk个元素需要时间为OO(kk)
\end{itemize}

\emph{ 一般来说,栈不允许“读取内部元素”,只能在栈顶操作。}

\textbf{栈的应用}\\
栈的特点:后进先出,体现了元素之间的透明性。\\
\textbf{常用来处理具有递归结构的数据}\\
\begin{itemize}
	\item 深度优先搜索
	\item 表达式求值
	\item 子程序/函数调用的管理
	\item 消除递归
\end{itemize}
\textbf{计算表达式的值}
\begin{itemize}
	\item 表达式的递归定义
	      \begin{itemize}
		      \item 基本符号集:{0,1,...,9,+,-,*,/,(,)}
		      \item 语法成分集:{<表达式> , <项> , <因子> , <常数>, <数字> }
	      \end{itemize}
	\item 中缀表达23+(34*45)/(5+6+7)式
	\item 后缀表达式23 34 45 * 5 6 + 7 + / +
\end{itemize}

\textbf{计算中缀表达式}
表达式：4 * x * (2 * x + a) – c
\begin{itemize}
	\item 运算符在中间
	\item 需要括号改变优先级
\end{itemize}
计算图如\ref{fig:ds_17}
\begin{figure}[!h]\label{fig:ds_16}
	\centering
	\includegraphics[width=0.5\textwidth]{ds_17.png}
	\caption{中缀表达式计算}
\end{figure}
中缀表达式的语法公式：
\begin{Textcode}
	<表达式> ::= <项> + <项>
	| <项> - <项>
	| <项>
	<项> ::= <因子> * <因子>
	| <因子> / <因子>
	| <因子>
	<因子> ::= <常数>
	| ( <表达式> )
	<常数> ::= <数字>
	| <数字> <常数>
	<数字> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
\end{Textcode}
表达式的递归图示\ref{fig:ds_16}
\begin{figure}[!ht]\label{fig:ds_16}
	\centering
	\includegraphics[width=0.5\textwidth]{ds_18.png}
	\caption{表达式的递归图示}
\end{figure}
后缀表达式\ref{fig:ds_19}：4 x * 2 x * a + * c –
\begin{itemize}
	\item 运算符在后面
	\item 完全不需要括号
\end{itemize}
\begin{figure}[!ht]\label{fig:ds_19}
	\centering
	\includegraphics[width=0.5\textwidth]{ds_19.png}
	\caption{后缀表达式示意图}
\end{figure}
后缀表达式
\begin{Textcode}
	<表达式>::=<项> <项> +
	| <项> <项> -
	| <项>
	<项>
	::= <因子> <因子> *
	| <因子> <因子> /
	| <因子>
	<因子>::=<常数>
	<常数>::=<数字>
	| <数字> <常数>
	<数字>::=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
\end{Textcode}
后缀表达式求值

\begin{itemize}
	\item  循环:依次顺序读入表达式的符号序列(假设
	      以=作为输入序列的结束),并根据读入的元
	      素符号逐一分析
	      \begin{enumerate}
		      \item 当遇到的是一个操作数,则压入栈顶
		      \item 当遇到的是一个运算符, 就从栈中两次取出栈顶,按照运算符对这两个操作数进行计算。然后将计算结果压入栈顶
	      \end{enumerate}
	\item 如此继续,直到遇到符号=,这时栈顶的值就
	      是输入表达式的值
\end{itemize}
\textbf{后缀计算器的类定义}\\
\begin{cpp}
	class Calculator {
			private:
			Stack<double> s;            // 这个栈用于压入保存操作数
			// 从栈顶弹出两个操作数opd1和opd2
			bool GetTwoOperands(double& opd1,double& opd2);
			// 取两个操作数,并按op对两个操作数进行计算
			void Compute(char op);
			public:
			Calculator(void){};        // 创建计算器实例,开辟一个空栈
			void Run(void);            // 读入后缀表达式,遇“=”符号结束
			void Clear(void);          // 清除计算器,为下一次计算做准备
		};
	template <class ELEM>
	bool Calculator<ELEM>::GetTwoOperands(ELEM& opnd1, ELEM& opnd2) {
			if (S.IsEmpty()) {
					cerr << "Missing operand!" <<endl;
					return false;
				}
			opnd1 = S.Pop(); // 右操作数
			if (S.IsEmpty()) {
					cerr << "Missing operand!" <<endl;
					return false;
				}
			opnd2 = S.Pop(); // 左操作数
			return true;
		}
	template <class ELEM> void Calculator<ELEM>::Compute(char op) {
			bool result; ELEM operand1, operand2;
			result = GetTwoOperands(operand1, operand2);
			if (result == true)
			switch(op) {
					case '+' : S.Push(operand2 + operand1); break;
					case '-' : S.Push(operand2 - operand1); break;
					case '*' : S.Push(operand2 * operand1); break;
					case '/' : if (operand1 == 0.0) {
							cerr << "Divide by 0!" << endl;
							S.ClearStack();
						} else S.Push(operand2 / operand1);
					break;
				}
			else S.ClearStack();
		}
	template <class ELEM> void Calculator<ELEM>::Run(void) {
			char c; ELEM newoperand;
			while (cin >> c, c != '=') {
					switch(c) {
							case '+': case '-': case '*': case '/':
							Compute(c);
							break;
							default:
							cin.putback(c); cin >> newoperand;
							S.Push(newoperand);
							break;
						}
				}
			if (!S.IsEmpty())
			cout << S.Pop() << endl; // 印出求值的最后结果
		}
\end{cpp}
\subsection{函数递归调用}
\begin{itemize}
	\item 阶乘
	      \begin{equation*}
		      f(n) =
		      \begin{cases}
			      x\times f(n-1)\quad  n\geq 1 \\
			      1\quad n=1
		      \end{cases}
	      \end{equation*}

	\item 递归出口
	      \begin{itemize}
		      \item 递归终止的条件,即最小子问题的求解
		      \item 可以允许多个出口
	      \end{itemize}

	\item  递归规则(递归体+界函数)
	      \begin{itemize}
		      \item  将原问题划分成子问题
		      \item  保证递归的规模向出口条件靠拢
	      \end{itemize}
\end{itemize}
hanoi(n,X,Y,Z)
\begin{itemize}
	\item  移动n个环
	\item  X柱出发,将环移动到Z 柱
	\item  X、Y、Z都可以暂存(大盘不能压小盘)
\end{itemize}
河内塔示意图\ref{fig:ds_21}
\begin{figure}[!ht]\label{fig:ds_21}
	\centering
	\includegraphics[width=0.5\textwidth]{ds_21.png}
	\caption{河内塔示意图}
\end{figure}

\begin{cpp}
	void hanoi(int n, char X, char Y, char Z) {
			if (n <= 1)
			move(X,Z);
			else {                   // X上最大的不动,其他 n-1个环移到Y
					hanoi(n-1,X,Z,Y);
					move(X,Z);           // 移动最大环到Z,放好
					hanoi(n-1,Y,X,Z);    // 把 Y上的n-1个环移到Z
				}
		}
	void move(char X, char Y)        // 把柱X的顶部环移到柱Y
	{
	cout << "move" << X << "to" << Y << endl;
	}
\end{cpp}
递归调转示意图\ref{fig:ds_19}
\begin{figure}[!ht]\label{fig:ds_19}
	\centering
	\includegraphics[width=0.5\textwidth]{ds_19.png}
	\caption{递归转非递归}
\end{figure}
递归运行时，堆栈的进退以及通过堆栈传递参数
\begin{figure}[!ht]\label{fig:ds_20}
	\centering
	\includegraphics[width=0.5\textwidth]{ds_20.png}
	\caption{递归运行}
\end{figure}
\begin{equation*}
	\begin{cases}
		n+1\quad n<2 \quad \\
		f(n/2)*f(n/4) \quad n\geq 2
	\end{cases}
\end{equation*}
\begin{cpp}
	void exmp(int n,int & f)
	{
			int u1, u2;
			if (n<2)
			f = n+1;
			else {
					exmp((int)(n/2), u1);
					exmp((int)(n/4), u2);
					f = u1*u2;
				}
		}
\end{cpp}
\subsection{队列}
队列是一个简单的等待序列，在尾部加入元素时队列加长，在前端删除数据时队列缩短。和栈不同，队列是一种使用两端的结构：一端用来加入新元素，另一端用来删除元素。因此最后一个元素必须等到排在它之前的所有元素都删除后才能操作。队列是一种先进先出（FIFO）的结构。下面使用一维数组实现循环数组。循环数组作为一种数据结构只是在代码层面对这种结构做限制。如图\ref{fig:queue_circle}.判断循环队列有两种方式：
\begin{enumerate}\label{en:isfull}
	\item 第一个元素在第一个单元。最后一个元素在最后一个单元（a）。
	\item 第一个元素和最后一个元素相邻并在其右面。
\end{enumerate}
enqueue()可以看成循环数组上的操作(c)，但实际上这时在一维数组上操作。因此，如果最后一个元素在最后一个单元中，而且数组的开始单元为空，则将新元素放在开始单元（d）。如果最后一个元素在其它位置，且空间允许的话，新的元素就放到它的后面（e）。

循环队列结构：
\begin{figure}[H]\label{fig:queue_circle}
	\centering
	\includegraphics[width=\textwidth]{queue_circle.png}
	\caption{循环队列}
\end{figure}
\cppfile{code/DS/ex8/array_queue.hpp}
测试代码:
\cppfile{code/DS/ex8/main.cpp}
\cppfile[firstline=49,lastline=52]{code/DS/ex8/array_queue.hpp}
上面代码测试循环队列是否已满,如\ref{en:isfull}。
enqueue的时候有两种情况一种是（d）对应的最后一个元素在数组最后面，这个时候需要将一维数组的第一个元素作为环形队列的最后一个元素添加，last指向一维数组的第一个元素如果环形队列为空，则第一个元素指向一维数组的0位置。
\cppfile[firstline=23,lastline=29]{code/DS/ex8/array_queue.hpp}
出队包含三种情况：
\begin{enumerate}
	\item 第一个元素和最后一个元素指针指向同一个元素（指空）。
	\item first指向last-1，因为是环形队列，下一个元素就是first=0。
	\item first指针后移动一位。
\end{enumerate}
\subsection{优先队列}
在优先队列中，根据元素的优先级以及在队列中的当前位置决定出队列的顺序。在STL中实现了优先队列priority\_queue，priority\_queue容器默认使用deque容器总是把邮件即最高的元素放在队列的最前方以维持队列的顺序。为此插入push操作使用两个参数的的bool函数，将对列中的元素重新排序以满足这个要求，该函数可以使用<运算符，元素的值越大优先级越高。如果元素值越小优先级越高则需要使用函数greater表明在决定邮件队列中插入新元素push()应该应用运算符>而不是<。
优先队列的例子：
\cppfile{code/DS/ex9/main.cpp}
对类Person中年龄最大的输出。
\cppfile{code/DS/ex10//main.cpp}



















































